package com.bolang.onlycode.demo;

import java.util.Arrays;

public class MergeSort {

    public  static  void mergesort(int[] arr){
        int[] temparr=new int[arr.length];
        recursion(arr,0,arr.length-1,temparr);
    }
    //归并的分割数组
    public static void recursion(int[] arr, int left, int right,int[] temparr){

        if(left<right){
            // 计算出中间的位数，中间算左半边的最右。
            int mid=left+((right-left)>>1);
            // 递归左半部分，直到左半边不可再分为止
            recursion(arr,left,mid,temparr);
            // 当递归到左半部分的左边
            recursion(arr,mid+1,right,temparr);
            merge(arr,left,mid,right,temparr);


        }

    }
    public static void merge(int[] arr, int left,int mid, int right,int[] temparr){
              int temp1=left;
              int temp2=mid+1;
              int index=0;//临时数组初始索引
        while (temp1<=mid&&temp2<=right){
                 if(arr[temp1]<=arr[temp2]){
                     temparr[index++]=arr[temp1++];
                 }else {
                     temparr[index++]=arr[temp2++];
                 }
        }
        while (temp1<=mid){
            temparr[index++]=arr[temp1++];
        }
        while (temp2<=mid){
            temparr[index++]=arr[temp2++];
        }
        for (int i = 0; i < temparr.length; i++) {
            arr[i]=temparr[i];
        }
        }

    public static void main(String[] args) {
        int[] ints = {6, 1, 3, 5, 4,7,8,9};
        mergesort(ints);
        System.out.println(Arrays.toString(ints));
    }


}

